/**
 * 双端双向链表
 */
;(function(window, document){
	var Node = function(pKey, pData){
		return {
			key: pKey,
			data: pData,
			previous: null,
			next: null
		}
	};

	var DoubleLink = function(){
		this._head = null;
		this._tail = null;
	};
	DoubleLink.prototype = {
		constructor: DoubleLink,
		prepend: function(pKey, pData){
			var node = Node(pKey, pData);
			if( this.isEmpty() ){
				this._tail = this._head = node;
				return;
			}
			this._head.previous = node;
			node.next = this._head;
			this._head = node;
		},
		append: function(pKey, pData){
			var node = Node(pKey, pData);
			if( this.isEmpty() ){
				this._tail = this._head = node;
				return;
			}
			this._tail.next = node;
			node.previous = this._tail;
			this._tail = node;
		},
		deleteTail: function(){
			if( this.isEmpty() ) throw new Error('链表已空');
			// 如果只有一个元素
			if( this._tail.previous == null ){
				this._head = this._tail = null;
				return;
			}
			this._tail.previous.next = null;
			this._tail = this._tail.previous;
		},
		deleteHead: function(){
			if( this.isEmpty() ) throw new Error('链表已空');
			// 如果只有一个元素
			if( this._head.next == null ){
				this._head = this._tail = null;
				return;
			}
			this._head.next.previous = null;
			this._head = this._head.next;
		},
		insertAfter: function(pTarget, pKey, pData){
			var newNode = Node(pKey, pData);
			var node = this._head;
			while( node != null ){
				if( node.key == pTarget ){
					newNode.next = node.next;
					newNode.previous = node;
					if( node.next != null ){
						// 不在尾部插入
						node.next.previous = newNode;
					}else{
						// 在尾部插入
						this._tail = newNode;
					}
					node.next = newNode;
					return true;
				}
				node = node.next;
			}
			return false;
		},
		isEmpty: function(){
			return this._head == null;
		},
		toString: function(){
			var result = [],
				node = this._head;
			result.push('[');
			while( node != null ){
				var next = node.next ? node.next.key : 'null';
				var prev = node.previous ? node.previous.key : 'null';
				result.push(''+node.key+'[next:'+next+',prev:'+prev+']'+'-->\n\t');
				node = node.next;
			}
			result.push('null]');
			return result.join('');
		}
	};
	window.DoubleLink = DoubleLink;
})(window, document);